Several techniques arc known to speed-up reduction of an array of partial products in a multiplier. One well known technique is a Wallace tree. Another known technique to speed-up reduction of partial product terms in a multipler is described in "An Architecture For High Speed Array Multiplier" published by F. F. Islam and K. Tamaru in IEICE Transaction Fundamentals, Volume E76-A, No. 8, August 1993, pages 1326-1333. The speed-up technique disclosed by Islam and Tamaru provides the sum input to a linear array of adders as an input to the last adder in the the linear array, shifts the partial product input of each adder to the adder above (except the uppermost adder) but does not provide any speed-up in adding the partial products.
Another known technique to speed-up reduction of partial product terms in a multiplier is described in "Array Multiplication Scheme Using Counters and Pre-Addition" published by S. Vassiliadis, J. Hoekstra and H.-T. Chin in Electronic Letters, Volume 31, No. 8, Apr. 13, 1995, pages 619-620. The column-by-column reduction speed-up technique disclosed has three aspects. Firstly, all partial products are provided to adders early in the column addition sequence, three partial products per adder, until all of the adder inputs are utilized. Secondly, the sum input is provided as an input to the last adder in the column so as to minimize the delay to the sum output. Thirdly, to minimize the number of adders, inputs are provided to each of the adders until each adder, with the exception of at most one adder, has three inputs. Of course, each adder also has a carry output and a sum output. A shortcoming of the Vassiliadis et al technique is that partial products generated at one location must be added at another location which complicates routing of conductors, thereby enlarging the area of the multiplier.
What is needed is a technique for reducing partial product arrays that provides the advantage of speeding up adding the partial products while not complicating routing of conductors as in the Vassiliadis et al technique.